/*
x 的 y 次方

描述
求 x 的 y 次方，结果模10007

输入
一个正整数 x 和一个用数组表示的 y，如 [2, 0, 0] 表示 200
1 ≤ x≤ 2 ^ 31 -1
1≤y 数组长度≤ 2000
0≤ y 数组中的元素≤ 9
y 数组不会以 0开始，即不会出现类似 [0, 1, 0] 这种情况

输出
x ^ y的值，结果模 10007
*/

#include <stdio.h>
#include <math.h>
int modxy(int x, int y, int k) //根据分配率求模
{
	int a = 0;
	if (y == 1)
	{
		a = (int)pow(x, y) % k;
		return a;
	}
	if (y == 0)
	{
		a = 1;
		return a;
	}
	if (y % 2 == 0)
	{
		a = modxy(x, y / 2, k) * modxy(x, y / 2, k) % k;
	}
	else
	{
		a = (modxy(x, y / 2, k) * modxy(x, y / 2, k) % k) * modxy(x, 1, k) % k;
	}
	return a;
}

int solve(int x, int *y, int n)
{
	int k = 10007;
	int a;
	a = modxy(x, y[0], k); //最内层为x^y[0]mod10007
	for (int i = 1; i < n; i++)
	{
		a = (modxy(a, 10, k) % k) * modxy(x, y[i], k) % k; //每次循环都是((a^10mod10007)*(x^y[i])mod10007)的积再mod10007
	}
	return a;
}

int main()
{
	int x = 2147483647, n = 31, y[100] = {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, a;
	a = solve(x, y, n);
	printf("%d", a);
}